import java.util.HashMap;
import java.util.Map;

/**
 * 输入一个复杂链表
 * （每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），
 * 返回结果为复制后复杂链表的head。
 * （注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
 */
public class Solution35 {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }

        RandomListNode result = new RandomListNode(pHead.label);
        RandomListNode cur = result;
        RandomListNode curP = pHead;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        map.put(pHead, result);

        // 1.赋值next结点，并且创建对应的map，方便下一步的时候找到对应的random结点
        while (curP != null) {
            if (curP.next == null) {
                cur.next = null;
            } else {
                cur.next = new RandomListNode(curP.next.label);
                map.put(curP.next, cur.next);
            }
            cur = cur.next;
            curP = curP.next;
        }

        // 2.赋值random结点
        cur = result;
        curP = pHead;
        while (curP != null) {
            // 用curP的ramdom做key， 去取value
            cur.random = map.get(curP.random);
            curP = curP.next;
            cur = cur.next;
        }
        return result;
    }
}
